// based on http://www.cs.nott.ac.uk/~ctm/Idiom.pdf
package examples.tcpoly.idioms

trait Typefuns {
  type Id[+X] = X
  trait Const1[T] { type Apply[+X] = T }
  trait Partial1[M[_, +_], T] { type Apply[+X] = M[T,X] }

  trait PolyFun1[From[_], To[_], Bound[_], Lower] {
    def apply[T >: Lower](x: From[T])(implicit c: T => Bound[T]): To[T]
  }
}

trait Idioms extends Typefuns {
  implicit def curry2[a, b, c](f: (a, b) => c): a => b => c = (a: a) => (b: b) => f(a, b)
  implicit def curry3[a, b, c, d](f: (a, b, c) => d): a => b => c => d= (a: a) => (b: b) => (c: c) => f(a, b, c)
  trait Idiom[I[_]] {
    def ^^[T](x: T): I[T] 
    def <>[S, T](f: I[S => T], a: I[S]): I[T] 
    
    class FunCarrier[S, T](val payload: I[S => T]) {      
      def >>(a: I[S]): I[T] = <>(payload, a)
    }
    class IdiCarrier[S, T](val payload: I[S => T]) {      
      def >>(a: I[S]): I[T] = <>(payload, a)
    }    
    /*implicit*/ def c[S, T](x: S => T) = new FunCarrier[S, T](^^(x))
    def c2[S, T, U](x: (S, U) => T) = new FunCarrier[S, U => T](^^(x))
    def c3[S, T, U, V](x: (S, U, V) => T) = new FunCarrier[S, U => V => T](^^(x))
    /*implicit*/ def a[S, T](idif: I[S => T]) = new IdiCarrier[S, T](idif)    
  }

  // make a data structure idiomatically traversable
  trait IFunctor[+Self, Bound[_]] {
    // the implementation of this method must apply f to every substructure that meets the Bound of this functor
    type InjFun[I[+_]] = PolyFun1[Id, I, Bound, Self]
    def inject[I[+_]](f: InjFun[I])(implicit idi: Idiom[I]): I[Self]
    // TODO: this function has to be implemented for every different Bound[_], then it suffices to implement inject once per datastructure, irrespective of Bound[_]
    // def check[I[+_], T](x: T)(f: InjFun[I])(implicit idi: Idiom[I]): I[Self] = x match { case y : Bound[T] => f(y) case _ => idi.^^(x)  }
  }

  implicit object identityIdiom extends Idiom[Id] {
    def ^^[a](x: a) = x
    def <>[S, T](f: S => T, a: S) = f(a)
  }
}


//int monoid
trait MonoidIdioms extends Idioms {
  class MonoidIdiom[M[_], T](init: M[T], op: (M[T], M[T]) => M[T]) extends Idiom[Const1[M[T]]#Apply] {
    def ^^[a](x: a) = init
    def <>[X, Y](f: M[T], a: M[T]) = op(f, a)
  }

  implicit object booleanAndIdiom extends MonoidIdiom[Id, Boolean](true, _ && _)
  implicit object integerPlusIdiom extends MonoidIdiom[Id, Int](0, _ + _)
  implicit def ListConcatIdiom[T] = new ListConcatIdiom[T]
  class ListConcatIdiom[T] extends MonoidIdiom[List, T](Nil, _ ::: _)  

}

/*  object listIdiom extends Idiom[List] {
    def ^^[a](x: a) = List(x) 
    def <>[S, T](f: List[S => T], a: List[S]) 
      = (for((fun, arg) <- f zip a) yield fun(arg)).toList
  }  */
/*
trait ComposingIdioms extends Idioms {
//int monoid
case class ParIdiom[ia <: Idiom, ib <: Idiom](idiomA: ia, idiomB: ib) extends Idiom {
  type m[a]=(idiomA.m[a], idiomB.m[a]) 
  
  def par[a, b](f: a => idiomA.m[b], g: a => idiomB.m[b])(x: a): m[b] = (f(x), g(x))  
  
  def fmap[a, b](f: a => b)(x: m[a]): m[b] = x match {
    case (a, b) => (idiomA.fmap(f)(a), idiomB.fmap(f)(b))
  }
  
  def lift[a](x: a): m[a] = (idiomA.lift(x), idiomB.lift(x))
  def combine[S, T](f: m[S => T], a: m[S]): m[T] = (f, a) match { 
    case ((fA, fB), (aA, aB)) => (idiomA.combine(fA, aA), idiomB.combine(fB, aB)) 
  }
}

case class SeqIdiom[ia <: Idiom, ib <: Idiom](idiomA: ia, idiomB: ib) extends Idiom {
  type m[a] = idiomA.m[idiomB.m[a]] 
  
  def seq[a, b, c](f: b => idiomB.m[c], g: a => idiomA.m[b])(x: a): m[c] = idiomA.fmap(f)(g(x))
  
  def fmap[a, b](f: a => b)(x: m[a]): m[b] = idiomA.fmap(idiomB.fmap(f))(x)
  
  def lift[a](x: a): m[a] = idiomA.lift(idiomB.lift(x))
  def combine[S, T](f: m[S => T], a: m[S]): m[T] = {
    val combine_ = curry(idiomB.combine((_: idiomB.m[S => T]), (_: idiomB.m[S])))
    idiomA.combine(idiomA.combine(idiomA.lift(combine_), f), a)
    // idiomB.combine(f, a) in idiomA
  }
}
}

trait Envs {
  trait Env[Key <: AnyRef, Val] extends (Key => Val) {
    def apply(k: Key): Val
    def update(k: Key, v: Val) = new Env[Key, Val] {
      def apply(kk: Key) = if(k eq kk) v else Env.this(kk)
      def toString(shown: List[Key]) = (if(!shown.contains(k)) k+" -> "+v+", " else "")+Env.this.toString(k::shown)
      override def toString = toString(Nil)
    }
    def toString(shown: List[Key]): String
  }
  
  def empty[a <: AnyRef, b] = new Env[a, b] {
    def apply(k: a): b = error("Empty environment")
    override def toString = ""; def toString(xs: List[a]) = ""
  }
}

trait EnvIdioms extends Envs with Idioms {
  type from <: AnyRef; type to
  class EnvIdiom extends Idiom {
    type m[x] = Env[from, to] => Env[from, to]
    def fmap[a, b](f: a => b)(x: m[a]): m[b] = (e: Env[from, to]) => x(e) // only care about effects, so can disregard f
    def lift[a](x: a): m[a] = (e: Env[from, to]) => e
    def combine[S, T](f: m[S => T], a: m[S]): m[T] = (e: Env[from, to]) => f(a(e))
  }
}*/